home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7926 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: news.mr.net!usenet
  2. From: John Cleland <clelaj@born.com>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Wed, 14 Feb 1996 14:30:49 -0600
  6. Organization: Born
  7. Message-ID: <31224679.6193@born.com>
  8. References: <4fr8be$ass@news.iconn.net>
  9. NNTP-Posting-Host: 204.73.78.51
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (Win95; I)
  14.  
  15. The Crow wrote:
  16. > 
  17. > Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  18. > given factorial.  For instance,
  19. > 
  20. > 5! = 120
  21. > 
  22. > so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  23. > Problem is, no matter how huge of a data-type you use, there isn't any way for
  24. > the computer to handle 1000!, it is however possible to find the last non-zero
  25. > digit somehow.  One thing I have tried is as I went through mulitplying the
  26. > series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the
  27. > trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i
  28. > am not really sure why.  If anyone has a clue how I can do this let me know.
  29.  
  30. Don't just strip the trailing zeros, remove all digits except the last non-zero
  31. digit (which is your output) and then multiply by the next number in your sequence.
  32. This keeps the numbers down to a managable level and gives the correct answer as
  33. no more significant digit can affect the value of the LSD.
  34.  
  35. If we have a function int LSD(int val) which computes the value of the least
  36. significant non-zero digit the pseudo C code should be something like :
  37.  
  38. int factLSD = 1;
  39. int i;
  40.  
  41. for (i = 1; i <= 1000; i++)
  42.   {
  43.   factLSD = LSD(i * factLSD);
  44.   print i, factLSD;
  45.   } 
  46.  
  47.  
  48. John
  49. john.cleland@born.com
  50.